import java.util.*;
public class HushBuck2<K,V> {
    //定义一个哈希节点静态类（泛型参数）
    static class Node<K,V>{
        public K key;
        public V val;
        public Node<K,V> next;

        public Node(K key,V val){
            this.key=key;
            this.val=val;
        }
    }

    //哈希桶有一个数组,数组的每一个元素都为一个节点
    public Node<K,V>[]array= (Node<K,V>[])new Node[8];
    public int useSize;
    //哈希表的负载因子(插入元素个数/数组长度时要进行数组的扩容)
    public static double DEFAOULT_BREAK=0.75;


    //哈希桶元素的插入
    public void put(K key,V val){
        //实例化待插入的节点
        Node node=new Node(key,val);
        //根据key值计算相应的哈希
        int hash=key.hashCode();
        int index=hash%array.length;

        //检查该数组下标对应的链表中是否已存在待插入节点的相同的key值
        //如果不存在则进行链表元素的头插法，已存在的话则更新key值对应节点
        //val值(哈希表中不允许重复的key值但是可以有相同的val值)
        Node cur=array[index];
        while(cur!=null){
            if(cur.key==key){
                cur.val=node.val;
                return;
            }
            cur=cur.next;
        }
        //走到这一步则说明，该数组下标链表中不存在该节点的key值，接下来进行头插。
        node.next=array[index];
        array[index]=node;
        useSize++;
        //判断当前哈希表的负载因子是否超过限定值
        //如果查过则要进行数组的扩容(扩容过程中要包括每个节点的哈希地址重新计算，
        // 将所有原节点重新计算哈希地址)，所以数组的扩容一定不是简单的调用Arrays.copyOf()
        if(useSize/ array.length>=DEFAOULT_BREAK){
            resize();
        }
    }

    //数组的扩容
    public void resize(){
        //将数组大小进行二倍扩容
        Node<K,V>[]temp=(Node<K, V>[]) new Node[2* array.length];

        //遍历原数组中的所有节点并进行哈希地址的重算
        for(int i=0;i<array.length;i++){
            Node cur=array[i];

            //遍历链表当前数组下标对应的链表
            while(cur!=null){
                //储存cur的下一个节点，因为在下边cur.next会被修改导致无法找到cur的下一个节点是谁
                Node curNext=cur.next;
                //计算新的哈希地址
                int hash=cur.key.hashCode();
                int index=hash% temp.length;
                cur.next=temp[index];
                temp[index]=cur;
                cur=curNext;
            }
        }
        //扩容成功,将新数组的引用赋值给旧数组
        array=temp;
    }

    //根据key值获取对应的val值
    public V getValue(K key){
        int hash=key.hashCode();
        int index=hash% array.length;
        Node<K,V> cur=array[index];
        while(cur!=null){
            if(cur.key.equals(key)){
                return cur.val;
            }
            cur=cur.next;
        }
        return null;
    }
}
